/**
 * 912. 排序数组
 *
 * [中等]
 *
 * 给你一个整数数组 nums，请你将该数组升序排列。
 * 你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。
 *
 * 示例 1：
 * 输入：nums = [5,2,3,1]
 * 输出：[1,2,3,5]
 *
 * 示例 2：
 * 输入：nums = [5,1,1,2,0,0]
 * 输出：[0,0,1,1,2,5]
 */

function sortArray(nums: number[]): number[] {
	const { length } = nums
	if (length <= 1) return nums

	const midIndex = Math.floor(length / 2)

	const leftArr = sortArray(nums.slice(0, midIndex))
	const rightArr = sortArray(nums.slice(midIndex, length))

	return mergeArray(leftArr, rightArr)

	function mergeArray(nums1: number[], nums2: number[]): number[] {
		const len1 = nums1.length,
			len2 = nums2.length
		const res: number[] = []
		let i = 0,
			j = 0

		while (i < len1 && j < len2) {
			if (nums1[i] < nums2[j]) res.push(nums1[i++])
			else res.push(nums2[j++])
		}

		if (i < len1) return res.concat(nums1.slice(i))
		else return res.concat(nums2.slice(j))
	}
}
